#include <iostream>
#include <BinaryTree.hpp>

using namespace std;

class Solution
{
public:
    TreeNode *flattenAndReturn(TreeNode *root)
    {
        if (root->left == nullptr && root->right == nullptr)
        {
            return root;
        }
        else if (root->left == nullptr && root->right != nullptr)
        {
            return flattenAndReturn(root->right);
        }
        else if (root->left != nullptr && root->right == nullptr)
        {
            root->right = root->left;
            root->left = nullptr;
            return flattenAndReturn(root->right);
        }
        else if (root->left != nullptr && root->right != nullptr)
        {
            auto right = root->right;
            auto leftFlattenEnd = flattenAndReturn(root->left);
            root->right = root->left;
            root->left = nullptr;
            auto rightFlattenEnd = flattenAndReturn(right);
            leftFlattenEnd->right = right;
            return rightFlattenEnd;
        }
    }
    void flatten(TreeNode *root)
    {
        if (root == nullptr)
            return;
        flattenAndReturn(root);
    }
};

int main()
{
    cout << "Code114" << endl;
    Solution s;
    TreeNode *root = CreatTree("1,2", "null");
    s.flatten(root);
    PrintTreeByWide(root, "null", 6);
    return 0;
}